VoIP technologies have become ubiquitous for carrying out conversations over data networks, such as over the Internet. A typical VoIP service (e.g., Skype) maintains a persistent network connection between a client-side VoIP application—e.g., installed on a mobile computing device—and a server system associated with the VoIP service. The persistent network connection is maintained over cellular networks and/or WiFi networks. To keep the persistent network connection open and avoid firewall or network address translation (NAT) related timeouts, the foregoing components of the VoIP service repeatedly exchange messages (e.g., keep-alive packets). In this manner, a VoIP service sends keep-alive packets periodically either from its server to the mobile computing device or vice-versa, e.g., every few minutes, to ensure that the connection with the mobile computing device does not timeout. This results in battery drain on the mobile computing device that can represent a large fraction of the total power consumption of the mobile computing device.